package geekstudy.week6;

import java.util.Arrays;

/**
 *
 * 673. 最长递增子序列的个数
 * https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：20 ms, 在所有 Java 提交中击败了92.30% 的用户
 * 内存消耗：38.1 MB, 在所有 Java 提交中击败了48.18% 的用户
 *
 */
public class Week6NumberOfLongestIncreasingSubsequence {

    public int findNumberOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int[] dynamicPlan = new int[nums.length];
        int[] combination = new int[nums.length];

        Arrays.fill(dynamicPlan, 1);
        Arrays.fill(combination, 1);

        int max = 1, result = 0;

        for (int i = 1; i < dynamicPlan.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dynamicPlan[j] + 1 > dynamicPlan[i]) {

                        dynamicPlan[i] = dynamicPlan[j] + 1;
                        combination[i] = combination[j];
                    } else if (dynamicPlan[j] + 1 == dynamicPlan[i]) {

                        combination[i] += combination[j];
                    }
                }
            }
            max = Math.max(max, dynamicPlan[i]);
        }

        for (int size = 0; size < nums.length; size++){
            if (dynamicPlan[size] == max) {
                result += combination[size];
            }
        }


        return result;
    }
}
